from copy import deepcopy


class Solution:
    def solve(self, board: list) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if len(board) == 0:
            return
        self.length, self.heigh = len(board[0]), len(board)
        self.mid_mat = deepcopy(board)
        for j in range(self.length):
            if self.mid_mat[0][j] == "O":
                self.change(0, j)
            if self.mid_mat[self.heigh - 1][j] == "O":
                self.change(self.heigh - 1, j)
        for i in range(1, self.heigh - 1):
            if self.mid_mat[i][0] == "O":
                self.change(i, 0)
            if self.mid_mat[i][self.length - 1] == "O":
                self.change(i, self.length - 1)
        for i in range(1, self.heigh - 1):
            for j in range(1, self.length - 1):
                if self.mid_mat[i][j] == "O":
                    board[i][j] = "X"

    def change(self, i, j):
        self.mid_mat[i][j] = "A"
        if i - 1 > 0 and self.mid_mat[i - 1][j] == "O":
            self.change(i - 1, j)
        if i + 1 < self.heigh - 1 and self.mid_mat[i + 1][j] == "O":
            self.change(i + 1, j)
        if j - 1 > 0 and self.mid_mat[i][j - 1] == "O":
            self.change(i, j - 1)
        if j + 1 < self.length - 1 and self.mid_mat[i][j + 1] == "O":
            self.change(i, j + 1)


class Solution2:
    """这个还不如上面快,会超时"""
    def solve(self, board: list) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if len(board) == 0:
            return
        self.length, self.heigh = len(board[0]), len(board)
        self.mid_mat, self.board = deepcopy(board), board
        for i in range(1, self.heigh - 1):
            for j in range(1, self.length - 1):
                if self.mid_mat[i][j] == "O" and self.mid_mat[i][j] =="O":
                    if not self.search(i, j):
                        board[i][j] = "X"
        # for lines in self.mid_mat:
        #     print(lines)

    def search(self, i, j):
        self.mid_mat[i][j] = "?"
        if self.board[i - 1][j] == "O":
            if i - 1 == 0 or self.mid_mat[i - 1][j] == "Y" or (self.mid_mat[i - 1][j] == "O" and self.search(i - 1, j)):
                self.mid_mat[i][j] = "Y"
                return True
        if self.board[i][j - 1] == "O":
            if j - 1 == 0 or self.mid_mat[i][j - 1] == "Y" or (self.mid_mat[i][j - 1] == "O" and self.search(i, j - 1)):
                self.mid_mat[i][j] = "Y"
                return True
        if self.board[i + 1][j] == "O":
            if i + 1 == self.heigh - 1 or self.mid_mat[i + 1][j] == "Y" or \
                    (self.mid_mat[i + 1][j] == "O" and self.search(i + 1, j)):
                self.mid_mat[i][j] = "Y"
                return True
        if self.board[i][j + 1] == "O":
            if j + 1 == self.length - 1 or self.mid_mat[i][j + 1] == "Y" or \
                    (self.mid_mat[i][j + 1] == "O" and self.search(i, j + 1)):
                self.mid_mat[i][j] = "Y"
                return True
        self.mid_mat[i][j] = "O"
        return False


a = Solution2()
# b = [["X", "X", "X", "X"], ["X", "O", "O", "X"], ["X", "X", "O", "X"], ["X", "O", "X", "X"]]
# a.solve(b)
# print(b)
# b = [["O", "X", "X", "O", "X"],
#      ["X", "O", "O", "X", "O"],
#      ["X", "O", "X", "O", "X"],
#      ["O", "X", "O", "O", "O"],
#      ["X", "X", "O", "X", "O"]]
# a.solve(b)
# print(b)
# b = [["O", "X", "O"], ["X", "O", "X"], ["O", "X", "O"]]
# a.solve(b)
# print(b)
# b = [["O","O","O","O","X","X"],
#        ["O","O","O","O","O","O"],
#        ["O","X","O","X","O","O"],
#        ["O","X","O","O","X","O"],
#        ["O","X","O","X","O","O"],
#        ["O","X","O","O","O","O"]]
# a.solve(b)
# print(b)
# b = [["O","X","O","O","O","O","O","O","O"],
#      ["O","O","O","X","O","O","O","O","X"],
#      ["O","X","O","X","O","O","O","O","X"],
#      ["O","O","O","O","X","O","O","O","O"],
#      ["X","O","O","O","O","O","O","O","X"],
#      ["X","X","O","O","X","O","X","O","X"],
#      ["O","O","O","X","O","O","O","O","O"],
#      ["O","O","O","X","O","O","O","O","O"],
#      ["O","O","O","O","O","X","X","O","O"]]
# a.solve(b)
# print(b)
b = [["O","X","O","O","O","X"],
     ["O","O","X","X","X","O"],
     ["X","X","X","X","X","O"],
     ["O","O","O","O","X","X"],
     ["X","X","O","O","X","O"],
     ["O","O","X","X","X","X"]]
a.solve(b)
for lines in b:
    print(lines)
